#include <atomic>
#include <string>
#include <iostream>
#include <thread>

template <typename T>
struct node
{
    T data;
    node *next;
    node(const T &data) : data(data), next(nullptr) {}
};

template <typename T>
class stack
{
    std::atomic<node<T> *> head;

public:
    stack() : head(nullptr) {}

public:
    void push(const T &data);
    T pop();
};

template <typename T>
void stack<T>::push(const T &data)
{
    node<T> *new_node = new node<T>(data);

    // put the current value of head into new_node->next
    new_node->next = head.load(std::memory_order_relaxed);

    // now make new_node the new head, but if the head
    // is no longer what's stored in new_node->next
    // (some other thread must have inserted a node just now)
    // then put that new head into new_node->next and try again
    while (!head.compare_exchange_weak(new_node->next,
                                       new_node,
                                       std::memory_order_release,
                                       std::memory_order_relaxed))
        ; // the body of the loop is empty
}

template <typename T>
T stack<T>::pop()
{
    while (1)
    {
        auto result = head.load(std::memory_order_relaxed);

        if (result == nullptr)
            throw std::string("Cannot pop from empty stack");

        if (head.compare_exchange_weak(result, result->next,
                                       std::memory_order_release,
                                       std::memory_order_relaxed))
            return result->data;
    }
}

int main()
{
    stack<int> ss;

    bool state = true;

    std::thread([&ss, &state]()
                {
        while(state)
        {
        ss.push(11); 
        std::this_thread::sleep_for(std::chrono::milliseconds(50));
        } })
        .detach();

    std::thread([&ss, &state]()
                {
        while(state)
        {
        ss.push(22); 
        std::this_thread::sleep_for(std::chrono::milliseconds(50));
        } })
        .detach();

    while (state)
    {
        std::cout << ss.pop() << std::endl;
        std::this_thread::sleep_for(std::chrono::milliseconds(50));
    }

    state = false;
}
